package dfs;

/**
 * @author pengfei.hpf
 * @date 2020/2/13
 * @verdion 1.0.0
 * You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
 *
 * Find out how many ways to assign symbols to make sum of integers equal to target S.
 *
 * Example 1:
 * Input: nums is [1, 1, 1, 1, 1], S is 3.
 * Output: 5
 * Explanation:
 *
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 *
 * There are 5 ways to assign symbols to make the sum of nums be target 3.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/target-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindTargetSumWays {

    int count = 0;
    public int findTargetSumWays(int[] nums, int S){
        if(nums == null || nums.length ==0){
            return count;
        }
        dfs(nums, S, 0);
        return count;
    }

    private void dfs(int[] nums, int target, int index){
        if(index == nums.length){
            if(target == 0 ){
                count ++;
            }
            return;
        }

        dfs(nums, target - nums[index], 1+index);
        dfs(nums, target + nums[index], 1+index);

    }

    //dp
    public int findTargetSumWays_dp(int[] nums, int S){
        if(nums == null || nums.length ==0){
            return 0;
        }
        int[] dp = new int[2001];
        int sIndex = 1000;
        dp[nums[0] + sIndex] = 1;
        dp[-nums[0] + sIndex] += 1;
        for(int i = 1; i < nums.length; i ++){
            int[] tmp = new int[2001];
            for(int j = -1000; j <= 1000; j ++){
                if(dp[j + 1000] > 0){
                    tmp[j + nums[i] + sIndex] += dp[j+sIndex];
                    tmp[j - nums[i] + sIndex] += dp[j+sIndex];
                }
            }
            dp = tmp;
        }
        return S>1000? 0: dp[S+1000];
    }

}
